#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
#include<vector>
using namespace std;

typedef struct list_node
{
	struct list_node* next;
	struct list_node* prev;
	int data;

	list_node(int x)
		:next(nullptr)
		,prev(nullptr)
		,data(x)
	{}
}node;

class my_list
{
public:
	my_list()
		:head(nullptr)
	{}

	my_list(node*h, int s)
		:head(h)
		,sz(s)
	{}

	node* buyNewNode(int x)
	{
		node* newnode = new node(x);
		return newnode;
	}

	void Print()
	{
		assert(head);
		if (sz == 1)
		{
			cout << head->data << endl;
			return;
		}

		node* cur = head;
		int cnt = 0;
		while (cur->next && cnt < sz)
		{
			cout << cur->data;
			if (cnt != sz - 1) cout << "->";
			cur = cur->next;
			cnt++;
		}
		cout << endl;
	}

	void DListPushFront(int x)
	{
		node* newnode = buyNewNode(x);

		if (sz == 0)
		{
			head = newnode;
			head->next = head;
			head->prev = head;
			sz++;
			return;
		}

		newnode->next = head;
		newnode->prev = head->prev;
		head->prev->next = newnode;
		head->prev = newnode;
		head = newnode;
		sz++;
	}

	void DListPushBack(int x)
	{
		node* newnode = buyNewNode(x);

		if (sz == 0)
		{
			head = newnode;
			head->next = head;
			head->prev = head;
			sz++;
			return;
		}

		node* tail = head->prev;
		tail->next = newnode;
		newnode->prev = tail;
		head->prev = newnode;
		newnode->next = head;
		sz++;
	}

	void DListPopBack()
	{
		assert(head);
		node* tail = head->prev;
		tail->prev->next = head;
		head->prev = tail->prev;
		sz--;
	}

	void DListPopFront()
	{
		assert(head);
		node* first = head->next;
		first->prev = head->prev;
		head->prev->next = first;
		head = first;
		sz--;
	}

	int DListFind(int x)
	{
		assert(head);
		if (sz == 1)
		{
			if (head->data == x) return 1;
			else return -1;
		}

		node* cur = head;
		int cnt = 1;
		while (cnt <= sz)
		{
			if (cur->data == x) return cnt;
			cur = cur->next;
			cnt++;
		}
		return -1;
	}

	void DListUpperOrder()
	{
		vector<int> v;
		node* cur = head;
		int cnt = 0;
		while (cnt < sz)
		{
			v.push_back(cur->data);
			cur = cur->next;
			cnt++;
		}
		sort(v.begin(), v.end());
		my_list newl;
		for (auto e : v)
			newl.DListPushBack(e);
		head = newl.head;
	}

	void DListLowerOrder()
	{
		vector<int> v;
		node* cur = head;
		int cnt = 0;
		while (cnt < sz)
		{
			v.push_back(cur->data);
			cur = cur->next;
			cnt++;
		}
		sort(v.begin(), v.end(), greater<int>());
		my_list newl;
		for (auto e : v)
			newl.DListPushBack(e);
		head = newl.head;
	}

	pair<node*, int> DListCombine(my_list& bl)
	{
		node* h1 = head;
		int sz1 = sz, cnt1 = 0;
		node* h2 = bl.head;
		int sz2 = bl.sz, cnt2 = 0;
		my_list l;
		while (cnt1 < sz1 && cnt2 < sz2)
		{
			if (h1->data >= h2->data) l.DListPushBack(h2->data), h2 = h2->next, cnt2++;
			else l.DListPushBack(h1->data), h1 = h1->next, cnt1++;
		}
		while (cnt1 < sz1) l.DListPushBack(h1->data), h1 = h1->next, cnt1++;
		while (cnt2 < sz2) l.DListPushBack(h2->data), h2 = h2->next, cnt2++;
		return {l.head, l.sz};
	}

private:
	node* head;
	int sz = 0;
};